//请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果
//一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 
//
// [["a","b","c","e"], 
//["s","f","c","s"], 
//["a","d","e","e"]] 
//
// 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。 
//
// 
//
// 示例 1： 
//
// 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "A
//BCCED"
//输出：true
// 
//
// 示例 2： 
//
// 输入：board = [["a","b"],["c","d"]], word = "abcd"
//输出：false
// 
//
// 提示： 
//
// 
// 1 <= board.length <= 200 
// 1 <= board[i].length <= 200 
// 
//
// 注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/ 
// Related Topics 动态规划 
// 👍 123 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

//Java：矩阵中的路径
public class PJzOffer12JuZhenZhongDeLuJingLcof{
    public static void main(String[] args) {
        Solution solution = new PJzOffer12JuZhenZhongDeLuJingLcof().new Solution();
        char[][] word=new char[][]{
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'},
        };
        solution.exist(word,"ABCCED");
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private final int direction[]={-1,0,1,0,-1};
        public boolean exist(char[][] board, String word) {
            if(board==null||board.length<=0){
                return false;
            }
            if(word.length()<=0){
                return true;
            }
            int m=board.length;
            int n=board[0].length;

            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(dfs(board,m,n,i,j,word)){
                        return true;
                    }
                }
            }

            return false;
        }

        public boolean dfs(char board[][],int m,int n,int x,int y,String word){
            if(x<0||x>=m||y<0||y>=n||board[x][y]!=word.charAt(0)){
                return false;
            }
            char[] chs=word.toCharArray();
            int len=word.length()-1;
            int level=0;
            int position[]=new int[]{x,y};
            Deque<int[]> stack=new ArrayDeque<>();
            stack.push(position);


            while(!stack.isEmpty()){
                if(level==len){
                    return true;
                }
                int tmp[]=stack.pop();
                x=tmp[0];
                y=tmp[1];
                char ch= board[x][y];
                board[x][y]='/';
                for(int i=0;i<4;i++){
                    int _x=tmp[0]+direction[0];
                    int _y=tmp[1]+direction[1];
                    if(_x>=0&&_x<m&&_y>=0&&_y<n&&level<len&&board[_x][_y]==chs[level+1]){
                        stack.push(new int[]{_x,_y});
                       // board[_x][_y]='/';
                        level++;
                    }
                }
            }



            return false;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
